package leetcode.code2092;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 1. 排序。按照会议时间排序，开会从先到后。因为知道秘密肯定是按照时间顺序发生的。先同知道的人开会，获知秘密，再在时间轴上向后传递。 2.
 * 收集同一场会议的与会人员。收集完同一场会议的与会人员，将同一场会议的人员进行合并。 + 用并查集合并。 3. 合并完成之后，检查这场会议的与会人员 +
 * 谁知道秘密，知道秘密的添加到结果集中。知道秘密的人在并查集中，永远在同一个父节点0的支配下。为此最开始给0的size最大，保证所有和0`在union时`相关的集合都会挂到0下。最开始firstperson就挂到0下。
 * + 谁不知道秘密，不知道秘密的人员的集合需要分开。不知道秘密的人，一堆儿堆儿的都要分开成单个人，不然后续开会挂集合就乱了。 +
 * 知道秘密的判断依据，`并查集中父亲是0的知道秘密` 4. 合并所有会议之后，获得并查集中的`Set<Integer>
 * know`，这里包含知道秘密的所有人。
 */
public class Solution extends Solution2092 {

	class UnionFind {
		int[] father;
		int[] size;
		private Set<Integer> know;
		int[] stack;
		int pstack;

		public UnionFind(int n, int firstPerson) {
			this.father = new int[n];
			this.size = new int[n];
			this.stack = new int[n];
			this.pstack = -1;
			for (int i = 0; i < n; i++) {
				father[i] = i;
				size[i] = 1;
			}
			father[firstPerson] = 0;
			this.size[0] = n;
			this.size[firstPerson] = 0;
			know = new HashSet<>();
			know.add(0);
			know.add(firstPerson);
		}

		private int findFather(int person) {
			int ans = 0;
			while ((ans = this.father[person]) != person) {
				this.stack[++this.pstack] = person;
				person = ans;
			}
			while (this.pstack > -1) {
				this.father[this.stack[this.pstack--]] = ans;
			}
			return ans;
		}

		public void union(int person1, int person2) {
			int father1 = this.findFather(person1);
			int father2 = this.findFather(person2);
			if (father1 != father2) {
				int size1 = this.size[father1];
				int size2 = this.size[father2];
				if (size1 > size2) {
					this.size[father1] += size2;
					this.size[father2] = 0;
					this.father[father2] = father1;
				} else {
					this.size[father2] += size1;
					this.size[father1] = 0;
					this.father[father1] = father2;
				}
			}
		}

		public boolean isKnown(int person) {
			return this.findFather(person) == 0;// 父亲是0的知道秘密
		}

		public void disUnion(int person) {// 不知道秘密的分开
			this.father[person] = person;
			this.size[person] = 1;
		}

		public void disUnion(int persion1, int persion2) {
			if (!isKnown(persion1)) {// 分开不知道秘密的人
				disUnion(persion1);
			} else {
				know.add(persion1);// 知道秘密的添加到结果set中
			}
			if (!isKnown(persion2)) {// 分开不知道秘密的人
				disUnion(persion2);
			} else {
				know.add(persion2);
			}
		}

		public List<Integer> getAns() {// 获得问题结果
			return new ArrayList<>(know);
		}

	}

	@Override
	public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
		UnionFind uf = new UnionFind(n, firstPerson);// 知情人并查集
		int m = meetings.length;
		Arrays.sort(meetings, (a, b) -> a[2] - b[2]);// 按时间开会
		int[][] persons = new int[m][2];// 记录同一场会议的所有人
		int group = 0;// 这一个时间点的会议由多少组
		int lastTime = -1;
		for (int i = 0; i < m; i++) {
			int[] meeting = meetings[i];// 会议信息
			if (meeting[2] != lastTime) {// 不同于之前的会议
				updateSecret(persons, group, uf);// 更新这个会议的知情人
				lastTime = meeting[2];// 新开会时间
				persons[0][0] = meeting[0];// 这个时间段第一个开会的两个人
				persons[0][1] = meeting[1];
				group = 1;
			} else {
				persons[group][0] = meeting[0];
				persons[group][1] = meeting[1];
				group += 1;
			}
		}
		updateSecret(persons, group, uf);
		return uf.getAns();
	}

	private void updateSecret(int[][] persons, int size, UnionFind uf) {
		for (int i = 0; i < size; i++) {// 合并开会人的集合
			uf.union(persons[i][0], persons[i][1]);
		}
		for (int i = 0; i < size; i++) {// 分开不知道秘密的人
			uf.disUnion(persons[i][0], persons[i][1]);
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
